/**

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点 root。

就像之前的问题那样，给定的树是从表 A（root = Construct(A)）递归地使用下述 Construct(A) 例程构造的：

如果 A 为空，返回 null
否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
root 的左子树将被构建为 Construct([A[0], A[1], ..., A[i-1]])
root 的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
返回 root
请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A).

假设 B 是 A 的副本，并附加值 val。保证 B 中的值是不同的。

返回 Construct(B)。

 

示例 1：



输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：A = [1,4,2,3], B = [1,4,2,3,5]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


 ///////////////////////////////////////////////
 //利用中序遍历重构出 数组，再重建树B
class Solution {
public:
    void visit_In(TreeNode* node,vector<int> & arr)
    {
        if(node == 0)
            return ;
        visit_In(node->left, arr);
        arr.push_back(node->val);
        visit_In(node->right, arr);
    }
    int getIndexOfMaxValue(vector<int>& nums,int l,int r)
    {
        int maxIndex = l;
        int maxValue = nums[maxIndex];
        for(int i=l;i<=r;i++)
        {
            if(nums[i]>maxValue)
            {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
    TreeNode* constructMaximumBinaryTreeHelper(vector<int>& nums,int l,int r)
    {
        if(l > r)
            return 0;
        if(l==r)
            return new TreeNode(nums[l]);  

        int maxIndex = getIndexOfMaxValue(nums,l,r);
        TreeNode * node = new TreeNode(nums[maxIndex]);
        node->left = constructMaximumBinaryTreeHelper(nums, l, maxIndex-1);
        node->right = constructMaximumBinaryTreeHelper(nums, maxIndex+1, r);
        return node;

    }
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        vector<int> result;
        visit_In(root,result);
        result.push_back(val);
        return constructMaximumBinaryTreeHelper(result,0,result.size()-1);
    }
};


////////////////////////////////////////
//插入

// 类似于树的旋转，先保证最后性，
// 然后通过旋转保证最大性。
// 1. 不能有右儿子，因此从自己当右儿子开始
// 2. 向上比较，如果小于父节点，结束
// 3. 否则，如果自己有左儿子，则让出左儿子给父亲当右儿子，将父亲当做自己的左儿子
// 自己是爷爷的右儿子，重复该过程。



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        TreeNode * newNode = new TreeNode(val);
        TreeNode * node = root, * parent = 0;

        while (node)
        {
            if(node->val > val )
            {
                parent = node;
                node=node->right;
            }
            else
            {
                if(parent)
                {
                    parent->right = newNode;
                    newNode->left = node;
                    return root;
                }
                else{
                    newNode->left = node;
                    return newNode;
                }
            }
        }
        parent->right = newNode;
        return root;
    }
};